package J1_21;

import org.w3c.dom.ls.LSInput;

import java.util.List;

public class test {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    /*给你单链表的头结点 head ，请你找出并返回链表的中间结点。
    如果有两个中间结点，则返回第二个中间结点。*/
    public ListNode middleNode(ListNode head) {
        ListNode slow = new ListNode();
        ListNode fast = new ListNode();
        slow = head;
        fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    //输入一个链表，输出该链表中倒数第k个结点。
    public ListNode FindKthToTail(ListNode head,int k) {

        if(head == null) {
            return null;
        }
        ListNode cur = head;
        ListNode curKth = head;
        while (k != 1) {
            curKth = curKth.next;
            if(curKth == null) {
                return null;
            }
            k--;
        }
        while (curKth.next != null) {
            cur = cur.next;
            curKth = curKth.next;
        }
        return cur;
    }

    //将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newH = new ListNode();
        ListNode tmp = newH;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                tmp.next = list1;
                tmp = tmp.next;
                list1 = list1.next;
            } else {
                tmp.next = list2;
                tmp = tmp.next;
                list2 = list2.next;
            }
        }

        if (list1 == null) {
            tmp.next = list2;
        }
        if (list2 == null) {
            tmp.next = list1;
        }
        return newH.next;
    }


    //现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
    public ListNode partition(ListNode pHead, int x) {
        if (pHead == null || pHead.next == null) {
            return pHead;
        }
        ListNode newH = new ListNode();
        ListNode tmp = newH;
        ListNode cur = pHead;
        ListNode curNext = cur.next;

        while (curNext.next != null) {
            if (curNext.val < x) {
                tmp.next = curNext;
                cur.next = curNext.next;
                tmp = tmp.next;
            } else {
                cur = cur.next;
            }
            curNext = cur.next;
        }
        if (pHead.val < x) {
            tmp.next = pHead.next;
            pHead.next = newH.next;
            return pHead;
        }
        tmp.next = pHead;
        return newH.next;
    }

    //对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
    //
    //给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

    public boolean chkPalindrome(ListNode A) {
        ListNode slow = A;
        ListNode fast = A;
        int count = 0;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            count++;
        }
        ListNode sNext = slow.next;
        ListNode tmp;
        while (sNext.next != null) {
            tmp = sNext.next;
            sNext.next = slow;
            slow = sNext;
            sNext = tmp;
        }
        sNext.next = slow;
        while (count != 0) {
            if (A.val != sNext.val) {
                return false;
            }
            A = A.next;
            sNext = sNext.next;
            count--;
        }
        return true;
    }

    //给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA;
        ListNode pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

    //给你一个链表的头节点 head ，判断链表中是否有环
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            if (slow == fast) {
                return true;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }

    //给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next ==null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}
